# 类说明：数据元素类型
# 类释义：该类拥有带排序的关键字key
class StaticTableElement(object):
    def __init__(self, key):
        self.key = key


# 类名称：SSTable
# 类说明：静态查找表的顺序存储结构
# 类释义：该类拥有一个数据元素类型的列表data和data的长度length
class StaticTable(object):
    def __init__(self):
        self.data = []
        self.length = 0

    # 创建数据元素类型列表
    def CreateSequenceTable(self, elements):
        self.length = len(elements)
        for i in range(self.length):
            self.data.append(StaticTableElement(elements[i]))

    # 打印待排序列表集合
    def TraverseSequenceTable(self):
        print("待排序列表为：")
        for i in range(self.length):
            print(self.data[i].key, end="\t")
        print()

    # 判断排序列表集合是否为空
    def SequenceIsEmpty(self):
        if self.length == 0:
            print("SST为空")
        else:
            print("SST不为空")

    # 折半查找函数
    def BinarySearch(self, key):
        low = 0
        high = self.length - 1
        while low <= high:
            mid = int((low + high) / 2)
            if key is self.data[mid].key:
                print(f"找到了，下标为{mid}")
                return mid
            elif key < self.data[mid].key:
                high = mid - 1
            elif key > self.data[mid].key:
                low = mid + 1
        return False


# 主程序
STdata = [9, 17, 25, 39, 42, 53]
ST = StaticTable()
ST.CreateSequenceTable(STdata)
ST.SequenceIsEmpty()
ST.TraverseSequenceTable()
ST.BinarySearch(17)

